package com.skh.array;

import java.util.TreeSet;

/**
 * 第三大的数
 */
public class ThirdMax {

    /**
     * 给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
     * <p>
     * 示例 1:
     * <p>
     * 输入: [3, 2, 1]
     * <p>
     * 输出: 1
     * <p>
     * 解释: 第三大的数是 1.
     * 示例 2:
     * <p>
     * 输入: [1, 2]
     * <p>
     * 输出: 2
     * <p>
     * 解释: 第三大的数不存在, 所以返回最大的数 2 .
     * 示例 3:
     * <p>
     * 输入: [2, 2, 3, 1]
     * <p>
     * 输出: 1
     * <p>
     * 解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
     * 存在两个值为2的数，它们都排第二。
     */

    /**
     * 思路:利用treeset的有序性和唯一性
     * @param nums
     * @return
     */
    public int thirdMax(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int num : nums) {
            set.add(num);
        }

        if (set.size() < 3) {
            return set.last();//返回最大的
        } else {
            set.pollLast();
            set.pollLast();
            return set.pollLast();
        }
    }

    public int thirdMax1(int[] nums) {

        Integer firstMax = null;
        Integer secondMax = null;
        Integer thirdMax = null;

        for (Integer i:nums) {
            if (i.equals(firstMax) || i.equals(secondMax) || i.equals(thirdMax)) {
                continue;
            }
            if (firstMax == null || i > firstMax) {
                thirdMax = secondMax;
                secondMax = firstMax;
                firstMax = i;
            } else if (secondMax == null || i > secondMax) {
                thirdMax = secondMax;
                secondMax = i;
            } else if (thirdMax == null || i > thirdMax) {
                thirdMax = i;
            }
        }
        if (thirdMax == null) {
            return firstMax;
        } else {
            return thirdMax;
        }


    }
}
